\section{附录}

\subsection{模算术}
\begin{frame}{模算术}

  \begin{definition}
    对$f,g,h\in P[x]$, 若$h\mid f-g$, 我们记$f\equiv g\left(\mod h\right)$, 
  读作$f,g$模$h$ \emph{同余}（或直接说模$h$相等）。 
\end{definition}
\pause
同余形式的运算也称为\emph{模算术}。

\pause
\begin{proposition}\label{14E}
  \begin{enumerate}
    \item 同余关系满足
      \begin{itemize}
        \item （自反性）$f\equiv f\left(\mod h\right)$.
        \item （对称性）若$f\equiv g\left(\mod h\right)$, 则$g\equiv f\left(\mod h\right)$.
        \item （传递性）若$f\equiv g\left(\mod h\right), g\equiv k\left(\mod h\right)$, 则$f\equiv k\left(\mod h\right)$.
      \end{itemize}
      满足自反性、对称性、传递性的关系称为\emph{等价关系}，这样同余是等价关系。
      \pause
    \item 同余与多项式的加法、乘法相容：若$f_1\equiv g_1\left(\mod h\right), f_2\equiv g_2\left(\mod h\right)$,
      则
      \[
        f_1+f_2\equiv g_1+g_2\left(\mod h\right), \quad f_1f_2\equiv g_1g_2 \left(\mod h\right).
      \]
      特别地，$f\equiv g\left(\mod h\right)$蕴含了$f^m\equiv g^m\left(\mod h\right)$, 其中$m$是正整数。
  \end{enumerate}
\end{proposition}
\pause
  命题~\ref{14E}~表明模算术的行为是很良好的。
一般地，数学有个基本观念``商''，我们会在近世代数中细谈商群、商环。

\end{frame}


\begin{frame}
  \begin{proof}
  \begin{enumerate}
    \item 显然。
    \item 同余与加法相容显然，我们证明下同余与乘法相容。
      注意到
      \[
        f_1f_2-g_1g_2=(f_1-g_1)f_2+(f_2-g_2)g_1.
      \]
      这样$f_1\equiv g_1\left(\mod h\right), f_2\equiv g_2\left(\mod h\right)$时
      显然有$f_1f_2\equiv g_1g_2\left(\mod h\right)$.
  \end{enumerate}
\end{proof}

\pause
\begin{example}
  我们来证明$x^2+x+1$整除$x^{3m}+x^{3n+1}+x^{3p+2}$, 其中$m,n,p$是正整数。
  我们有
  \[
    x^2+x+1\mid x^3-1, \quad \text{即~} x^3\equiv 1\left(\mod x^2+x+1\right).
  \]
  进而
  \[
    x^{3k}\equiv 1\left(\mod x^2+x+1\right). 
  \]
  这样
  \[
    x^{3m}+x^{3n+1}+x^{3p+2} \equiv 1+ x + x^2 \equiv 0\left(\mod x^2+x+1\right).
  \]
  因此$x^2+x+1$整除$x^{3m}+x^{3n+1}+x^{3p+2}$.
\end{example}

\pause
\begin{exercise}
  给定正整数$n,m$, $x^n-1\mid x^m-1$的条件是什么？
\end{exercise}

\end{frame}


\begin{frame}

%我们把之前的一些结论用同余的形式写出来。

\begin{proposition}\label{18F}
  \begin{enumerate}
    \item\label{18E}
      令$f,g,r\in P[x]$, 且$g\neq 0$. 若$f\equiv r\left(\mod g\right)$, 则$(f,g)=(g,r)$.
      特别地，$f,g$互素当且仅当$g,r$互素。
    \item $f,g$互素当且仅当存在$v\in P[x]$使得$vg\equiv 1\left(\mod f\right)$.
    \item 若$k$与$h$互素，且$kf\equiv kg\left(\mod h\right)$, 则$f\equiv g\left(\mod h\right)$.
  \end{enumerate}
\end{proposition}
\pause
\begin{proof}
  由引理~\ref{126}~可得 (1).
      (2) 是定理~\ref{11B}~的重述。再证明(3).
    $k,h$互素表明存在$v$使得$vk\equiv 1\left(\mod h\right)$. 
      既然$kf\equiv kg\left(\mod h\right)$, 两边乘$v$得$f\equiv g\left(\mod h\right)$.
\end{proof}
\pause
\begin{example}
  令$n$是正整数，我们证明$x^2+x+1$与$x^n+1$互素。
  显然$x^3\equiv 1\left(\mod x^2+x+1\right)$, 
      从而$x^{3k}\equiv 1\left(\mod x^2+x+1\right)$. 进而我们有
      \[
        x^n+1 \left(\mod x^2+x+1\right) \equiv \begin{cases}
          2 & \text{若$n=3k$},\\
          x+1\equiv -x^2 & \text{若$n=3k+1$},\\
          x^2+1\equiv -x & \text{若$n=3k+2$}.
        \end{cases}
      \]
      显然$2, -x^2, -x$都与$x^2+x+1$互素。
      由命题~\ref{18F}\eqref{用模算术表示带余除法与最大公因子的关系(1)} 
      知 $x^n+1$总与$x^2+x+1$互素。
\end{example}

\end{frame}

\subsection{分圆多项式}

\begin{frame}{分圆多项式}

我们知道在$\CC[x]$中有$x^n-1=\prod_{k=0}^{n-1}(x-\zeta_n^k)$, 其中$\zeta_n=\frac{2\pi i}{n}$.
按照定义$n$次\emph{分圆多项式}为 %$x^n-1$的因子，但不是任一$x^j-1$的因子，其中$j<n$. 换句话说，
\[
  \Phi_n(x)=\prod_{\zeta\text{~周期为~}n}(x-\zeta)=\prod_{(k,n)=1}(x-\zeta_n^k).
\]
其中单位根$\zeta$的\emph{周期}指最小正整数的$m$使得$\zeta^m=1$ (单位根$\zeta$的周期为$m$相当于说$\zeta$是$m$次本原单位根)。
下面会证明$n$次分圆多项式$\Phi_n$的次数为$\varphi(n)$, 其中$\varphi$是Euler函数，以及$\Phi_n$为整系数不可约多项式。前$10$个分圆多项式为
\[
  \begin{aligned}
    \Phi_1(x)&= x-1,\\
    \Phi_2(x)&= x+1,\\
    \Phi_3(x)&= x^2+x+1,\\
    \Phi_4(x)&= x^2+1,\\
    \Phi_5(x)&= x^4+x^3+x^2+x+1,\\
    \Phi_6(x)&= x^2-x+1,\\
    \Phi_7(x)&= x^6+x^5+x^4+x^3+x^2+x+1,\\
    \Phi_8(x)&= x^4+1,\\
    \Phi_9(x)&= x^6+x^3+1,\\
    \Phi_{10}(x)&= x^4-x^3+x^2-x+1.
  \end{aligned}
\]
\end{frame}


\begin{frame}
\begin{proposition}
  我们有如下关于分圆多项式的事实： 
  \begin{enumerate}
    \item 若$p$是素数，
      \[
        \Phi_p(x)=x^{p-1}+\cdots +x+1,
      \]
      且对整数$r\geqslant 1$, 
      \[
        \Phi_{p^r}(x)=\Phi_p(x^{p^{r-1}}).
      \]
    \item 若$n=p_1^{r_1}\cdots p_s^{r_s}$是正整数的素分解，则
      \[
        \Phi_n(x)=\Phi_{p_1\ldots p_s}(x^{p_1^{r_1-1}\ldots p_s^{r_s-1}}).
      \]
    \item 若$n>1$是奇数，则$\Phi_{2n}(x)=\Phi_n(-x)$.
    \item 若$p$是素数，且不整除$n$, 则
      \[
        \Phi_{pn}(x)=\frac{\Phi_n(x^p)}{\Phi_n(x)}.
      \]
      另一方面，若$p\mid n$, 则$\Phi_{pn}(x)=\Phi_n(x^p)$.
    \item $x^n-1=\prod_{d\mid n}\Phi_d(x)$. （这是不可约分解，我们可由此归纳地构造分圆多项式。）
    \item $\Phi_n(x)=\prod_{d\mid n}(x^d-1)^{\mu\left(\frac{n}{d}\right)},$ 其中$\mu$是M\"obius函数。
    \item 分圆多项式是整系数多项式。 
  \end{enumerate}
\end{proposition}

\end{frame}


\begin{frame}
\begin{proof}
  \begin{enumerate}
    \item $p$素数时，由定义显然有$\Phi_p(x)=x^{p-1}+\cdots +x+1$. 
      显然$\Phi_p(x^{p^{r-1}})$的所有复根是两两不同的$p^r$次本原单位根，所以$\Phi_{p^r}(x)=\Phi_p(x^{p^{r-1}})$.
    \item \ldots
    \item 由于$n$是奇数，我们有$\varphi(2n)=\varphi(2)\varphi(n)=\varphi(n)$. 另一方面，$\Phi_n(-x)$的$\varphi(n)$个复根都是$2n$次本原单位根。
    \item \ldots
    \item %由练习~\ref{B17}~知$n=\sum_{d\mid n}\varphi(d)$.
      %对每个$d\mid n$, 周期为$d$的单位根恰好为$\varphi(d)$个，所以
      %
      容易发现$x^n-1$的根的集合等于
      $\bigcup_{d\mid n}\{\text{周期为$d$的单位根}\}.$
      这样$x^n-1=\prod_{d\mid n}\Phi_d(x)$. 
    \item 考虑
      \[
        \begin{aligned}
          f\colon & \ZZ^+\rightarrow \QQ(x)^*, \quad n\mapsto x^n-1,\\
          g\colon & \ZZ^+\rightarrow \QQ(x)^*,\quad n\mapsto \Phi_n(x),
        \end{aligned}
      \]
      由(5)知$f(n)=\prod_{d\mid n} g(d)$. 这样M\"obius反演给出了$g(n)=\prod_{d\mid n}f(d)^{\mu\left( \frac{n}{d} \right)}$, 即
      \[
        \Phi_n(x)=\prod_{d\mid n}(x^d-1)^{\mu\left(\frac{n}{d}\right)}.
      \]

    \item 我们对$n$归纳来说明$\Phi_n(x)\in \ZZ[x]$. 若$n=1$, $\Phi_1(x)=x-1\in \ZZ[x]$.
      %; 若$n$是素数，亦有$\Phi_n(x)=x^{n-1}+\cdots+1\in \ZZ[x]$. 否则，
      若$n>1$, 由(5)及归纳假设可得分圆多项式$\Phi_n(x)\in \QQ[x]$.
    又$x^n-1$的容量是$1$, 而由归纳假设对所有$d<n$有$d$次分圆多项式是首一整系数多项式，故$\Phi_n(x)$的容量为$1$, 从而$\Phi_n(x)$是整系数多项式。
  \end{enumerate}
\end{proof}

\end{frame}


\begin{frame}
借用这些性质，我们进一步写出$11$至$20$次分圆多项式：
  我们有
  \[
    \begin{aligned}
      \Phi_{11}(x)&= x^{10}+x^{9}+\cdots+x+1,\\
      \Phi_{12}(x)&= \Phi_6(x^2)=x^4-x^2+1,\\
      \Phi_{13}(x)&= x^{12}+x^{11}+\cdots +x+1,\\
      \Phi_{14}(x)&= \Phi_7(-x)=x^6-x^5+x^4-x^3+x^2-x+1,\\
      \Phi_{15}(x)&= \frac{\Phi_3(x^5)}{\Phi_3(x)}=\frac{x^{10}+x^5+1}{x^2+x+1}=x^{8} - x^{7} + x^{5} - x^{4} + x^{3} - x + 1,\\
      \Phi_{16}(x)&= \Phi_2(x^{8})=x^8+1,\\
      \Phi_{17}(x)&= x^{16}+x^{15}+\cdots+x+1,\\
      \Phi_{18}(x)&= \Phi_9(-x)=x^{6}-x^3+1,\\
      \Phi_{19}(x)&= x^{18}+x^{17}+\cdots+x+1,\\
      \Phi_{20}(x)&= \Phi_{10}(x^2)=x^8-x^6+x^4-x^2+1.
    \end{aligned}
  \]

最后我们来证明

\begin{theorem}\label{12B}
    $\Phi_n(x)$是$\QQ[x]$中的不可约多项式。
  \end{theorem} 

  我们先证明如下断言。
\end{frame}


\begin{frame}
  \begin{assertion*}\label{12C}
  设$f$是$\Phi_n(x)$在$\ZZ$上的一个首一不可约因子，
  $\zeta\in \CC$为$f$的一个根，
  素数$p$不整除$n$. 那么$\zeta^p$是$f$的根。
\end{assertion*}
  \begin{proof*}[断言的证明]
  反证，假设$\zeta^p$不是$f$的根。
  $\zeta^p$显然和$\zeta$一样是一个周期$n$的本原单位根。
  令$\Phi_n(x)=f(x)h(x)$, 则$\zeta^p$是$h$的根，从而$\zeta$是$h(x^p)$的根。
  $f$不可约且$f$与$h(x^p)$有公共根表明$f(x)\mid h(x^p)$, 于是可写$h(x^p)=f(x)g(x)$.
  既然$f$是首一整系数多项式，$g$也是整系数的。
  这样
  \[
    h(x^p)\equiv h(x)^p\equiv f(x)g(x)\left(\mod p\right).
  \]
  特别地，若我们分别记$\bar{f},\bar{h}\in \FF_p[x]$为$f,h$的模$p$剩余，
  则$\bar{f}, \bar{h}$不是互素的（在$\FF_p[x]$中应用唯一因子分解定理）。
  但是$x^n-\bar{1}=\bar{f}\bar{h}$, 这样$x^n-\bar{1}$有重因子。
取导数容易发现这是不可能的。断言得证。
\end{proof*}


\begin{proof*}[定理~\ref{12B}~的证明]
  设$f$为$\Phi_n(x)$在$\ZZ$上的一个首一不可约因子，
  令$\zeta$是$f$的一个复根，那么$\zeta$也是$\Phi_n(x)$的根，从而$\zeta$是
  一个本原单位根。对满足$2\leqslant k\leqslant n$且$(k,n)=1$的正整数$k$, 
  将$k$分解为一些素数的乘积：$k=p_1p_2\cdots p_r$, 反复使用上面的断言，
  我们可由$f(\zeta)=0$推出$f(\zeta^{p_1})=0$, $f(\zeta^{p_1p_2})=0$, 
  $\cdots$, 最后$f(\zeta^{p_1p_2\cdots p_r})=0$, 即$f(\zeta^k)=0$.
  由于$\zeta^k$ ($1\leqslant k\leqslant n$, $(k,n)=1$) 恰好给出了所有的周期为$n$的
  本原单位根，我们有$f(x)=\Phi_n(x)$. 如此$\Phi_n(x)$不可约。
\end{proof*}
\end{frame}
